package sort;

import java.util.Arrays;

//归并排序，，时间复杂度 O(nlogn)，80000个数据下 <1s。
//归并排序需要一个额外的空间开销 ——> temp
public class MergeSort {
	public static void main(String[] args) {
		int[] array = {8, 4, 5, 7, 1, 3, 6, 2};
		int[] temp = new int[array.length];
		mergeSort(array, 0, array.length - 1, temp);
		System.out.println(Arrays.toString(array));
	}

	//分解+合并的方法
	public static void mergeSort(int[] array, int left, int rigth, int[] temp) {
		if (left < rigth) {
			int mid = (left + rigth) / 2;
			//向左递归分解
			mergeSort(array, left, mid, temp);
			//向右递归分解
			mergeSort(array, mid + 1, rigth, temp);

			//合并
			merge(array, left, rigth, mid, temp);

		}
	}


	/**
	 * 合并的方法
	 *
	 * @param array :原始数组
	 * @param left  ：左边的索引值
	 * @param rigth ：右边的索引值
	 * @param mid   ：中间的索引值
	 * @param temp  ：临时数组，做中转
	 */
	public static void merge(int[] array, int left, int rigth, int mid, int[] temp) {
		int i = left;//左边有序序列的，初始索引
		int j = mid + 1;//右边有序序列的初始索引
		int t = 0;//指向 temp 临时数组的代存值的索引

		//1.先把左右两边的数据，按大小，填充到 temp 中，直到左右两边，有一边处理完毕为止
		while (i <= mid && j <= rigth) {
			//左边的值小于等于右边的，把左边的填到 temp，并把对应的索引后移
			if (array[i] <= array[j]) {
				temp[t] = array[i];
				t++;
				i++;
			} else {//反之
				temp[t] = array[j];
				t++;
				j++;
			}
		}

		//2.把 1 中有剩余数据的数组，依次填充到 temp
		while (i <= mid) {
			//左边的序列还有剩余
			temp[t] = array[i];
			i++;
			t++;
		}
		while (j <= rigth) {
			//右边的序列还有剩余
			temp[t] = array[j];
			j++;
			t++;
		}

		//3，把 temp 的数据拷贝到 array,并不是每次都是所有数
		t = 0;//恢复索引
		int tempLeft = left;
		while (tempLeft <= rigth) {
			array[tempLeft] = temp[t];
			t++;
			tempLeft++;
		}
	}

}
